﻿//#include <iostream>
//#include <algorithm>
//
//using namespace std;
//const int N = 2e5 + 10;
//
//int n, l, r;
//int arr[N];
//int main()
//{
//	cin >> n >> l >> r;
//	for (int i = 1; i <= n; i++) cin >> arr[i];
//	sort(arr + 1, arr + n + 1);
//	long long ret = 0;
//
//	for (int i = 2; i <= n; i++)
//	{
//		int L, R;
//		// 左端点
//		int left = 1, right = i - 1;
//		while (left < right)
//		{
//			int mid = (left + right) / 2;
//			if (arr[mid] >= arr[i] - r) right = mid;
//			else left = mid + 1;
//		}
//		if (arr[left] >= arr[i] - r) L = left;
//		else L = left + 1;
//
//		// 右端点
//		left = 1, right = i - 1;
//		while (left < right)
//		{
//			int mid = (left + right + 1) / 2;
//			if (arr[mid] <= arr[i] - l) left = mid;
//			else right = mid - 1;
//		}
//
//		if (arr[left] <= arr[i] - l) 
//			R = left;
//		else 
//			R = left - 1;
//		
//		if (R >= L) ret += R - L + 1;
//	}
//
//	cout << ret << endl;
//
//	return 0;
//}

//#include <iostream>
//#include <algorithm>
//#include <vector>
//
//using namespace std;
//
//class Solution
//{
//    typedef long long LL;
//public:
//    int minDifference(vector<int>& a)
//    {
//        sort(a.begin(), a.end());
//        int n = a.size();
//        LL ret = INT_MAX;
//
//        for (int i = 0; i < n-1; i++)
//        {
//            ret = min(ret, (LL)a[i + 1] - a[i]);
//        }
//
//        return ret;
//    }
//};


//#include <iostream>
//#include <cmath>
//
//using namespace std;
//
//const int N = 15, M = 1010;
//
//int n;
//int a[N];
//bool st[M];
//int num;
//int ret = 1e9;
//
//bool is_num(int x)
//{
//	if (x <= 1)
//		return false;
//
//	for (int i = 2; i <= sqrt(x); i++)
//	{
//		if (x % i == 0)
//			return false;
//	}
//	return true;
//}
//
//void dfs(int pos)
//{
//	if (pos == n)
//	{
//		ret = min(ret, num);
//		return;
//	}
//
//	for (int i = 2; i <= a[pos]; i++)
//	{
//		if (a[pos] % i == 0 && is_num(i) && !st[i])
//		{
//			num += i;
//			st[i] = true;
//			dfs(pos + 1);
//
//			num -= i;
//			st[i] = false;
//		}
//	}
//
//}
//
//int main()
//{
//	cin >> n;
//	for (int i = 0; i < n; i++)
//		cin >> a[i];
//
//	dfs(0);
//
//	if (ret >= 1e9)
//		cout << -1 << endl;
//	else
//		cout << ret << endl;
//
//	return 0;
//}




//#include <iostream>
//#include <cmath>
//
//using namespace std;
//const int N = 15, M = 1010;
//
//int n, arr[N];
//bool use[M]; // 记录路径中⽤了哪些值
//int path; // 记录当前路径中所有元素的和
//int ret = 0x3f3f3f3f; // 统计最终结果
//
//bool isPrim(int x)
//{
//	if (x <= 1) return false;
//	for (int i = 2; i <= sqrt(x); i++)
//	{
//		if (x % i == 0) return false;
//	}
//	return true;
//}
//
//void dfs(int pos)
//{
//	if (pos == n)
//	{
//		ret = min(ret, path);
//		return;
//	}
//	// 枚举 arr[pos] 的所有没有使⽤过的素因⼦
//	for (int i = 2; i <= arr[pos]; i++)
//	{
//		if (arr[pos] % i == 0 && isPrim(i) && !use[i])
//		{
//			path += i;
//			use[i] = true;
//			dfs(pos + 1);
//			// 回溯 - 恢复现场
//			path -= i;
//			use[i] = false;
//		}
//	}
//}
//
//int main()
//{
//	cin >> n;
//	for (int i = 0; i < n; i++) cin >> arr[i];
//
//	dfs(0);
//
//	if (ret == 0x3f3f3f3f) cout << -1 << endl;	 
//	else cout << ret << endl;
//
//	return 0;
//}


//dd爱科学1.0
//https://ac.nowcoder.com/acm/problem/221822
//超时
//#include <iostream>
//#include <vector>
//#include <algorithm>
//
//using namespace std;
//
//int main() 
//{
//    int n;
//    cin >> n;
//    string geneSequence;
//    cin >> geneSequence;
//    vector<int> values(n);
//    for (int i = 0; i < n; ++i) 
//    {
//        values[i] = geneSequence[i] - 'A';
//    }
//    vector<int> dp(n, 1);
//    for (int i = 1; i < n; ++i) 
//    {
//        for (int j = 0; j < i; ++j) 
//        {
//            if (values[i] >= values[j]) 
//            {
//                dp[i] = max(dp[i], dp[j] + 1);
//            }
//        }
//    }
//    cout <<  n - *(max_element(dp.begin(), dp.end())) << endl;
//
//    return 0;
//}

//
// 
//#include <iostream>
//#include <string>
//
//using namespace std;
//const int N = 1e6 + 10;
//int n;
//string s;
//char dp[N]; // dp[i] 表⽰：⻓度为 i 的所有的⼦序列中，最⼩的末尾是多少
//int ret;
//
//int main()
//{
//	cin >> n >> s;
//	for (int i = 0; i < n; i++)
//	{
//		char ch = s[i];
//		// 找出 ch 应该放在哪个位置
//		if (ret == 0 || ch >= dp[ret])
//		{
//			dp[++ret] = ch;
//		}
//		else
//		{
//			// ⼆分出 ch 应该放的位置
//			int left = 1, right = ret;
//			while (left < right)
//			{
//				int mid = (left + right) / 2;
//				if (dp[mid] > ch) right = mid;
//				else left = mid + 1;
//			}
//			dp[left] = ch;
//		}
//	}
//
//	cout << n - ret << endl;
//
//	return 0;
//}


//#include <iostream>
//#include <vector>
//#include <algorithm>
//
//using namespace std;
//
//int n;
//string s;
//
//int func() 
//{    
//    cin >> n >> s;
//    
//    vector<int> v(n);
//    for (int i = 0; i < n; ++i) 
//    {
//        v[i] = s[i] - 'A';
//    }
//
//    vector<int> v1;
//    for (auto& x : v) 
//{
//        auto it = upper_bound(v1.begin(), v1.end(), x);
//        if (it == v1.end())
//        {
//            v1.push_back(x);
//        }
//        else 
//        {
//            *it = x;
//        }
//    }
//
//    return n - v1.size();
//}
//
//int main() 
//{
//    int cost = func();
//    cout << cost << endl;
//    return 0;
//}


//kanan和高音
//https://ac.nowcoder.com/acm/problem/26229

//#include <iostream>
////#include <vector>
////#include <algorithm>
////
//using namespace std;
//
//const int N = 2e5 + 10;
//
//int n;
//int a[N];
//
//int main()
//{
//	cin >> n;
//	for (int i = 0; i < n; i++)
//		cin >> a[i];
//
//	int left = 0, right = 1;
//	int ret = 1;
//	while (right < n)
//	{
//		if(a[right] - a[right-1] > 8)
//			left = right;
//		ret = max(ret, right + 1 - left);
//		right++;
//	}
//
//	cout << ret << endl;
//
//	return 0;
//}

//MT3 拜访
// https://www.nowcoder.com/practice/491828fc7d93459db450b344c2aaaeef?tpId=128&tqId=33770&ru=/exam/oj
//#include <iostream>
//#include <vector>
//#include <queue>
////#include <algorithm>
////
//using namespace std;
//
//class Solution
//{
//    int n1, m1;
//    int x1, y1, x2, y2;
//    int dist[15][15] = { 0 };
//    int count[15][15] = { 0 }; //走到当前位置最短方案的种数
//    int dx[4] = { 0,0,1,-1 };
//    int dy[4] = { 1, -1, 0,0 };
//
//    int bfs(vector<vector<int>>& CityMap)
//    {
//        memset(dist, -1, sizeof(dist));
//        queue<pair<int, int>> q;
//        q.push({ x1, y1 });
//        dist[x1][y1] = 0;
//        count[x1][y1] = 1;
//
//        while (q.size())
//        {
//            auto e = q.front(); q.pop();
//            int a = e.first;
//            int b = e.second;
//            for (int i = 0; i < 4; i++)
//            {
//                int x = a + dx[i];
//                int y = b + dy[i];
//                if (x >= 0 && x < n1 && y >= 0 && y < m1 && CityMap[x][y] != -1)
//                {
//                    if (dist[x][y] == -1)
//                    {
//                        dist[x][y] = dist[a][b] + 1;
//                        count[x][y] += count[a][b];
//                        q.push({x, y});
//                    }
//                    else
//                    {
//                        if (dist[a][b] + 1 == dist[x][y])
//                        {
//                            count[x][y] += count[a][b];
//                        }
//                    }
//                }
//            }
//        }
//
//        return count[x2][y2];
//    }
//
//public:
//    int countPath(vector<vector<int> >& CityMap, int n, int m)
//    {
//        n1 = n, m1 = m;
//        for (int i = 0; i < n; i++)
//        {
//            for (int j = 0;j <m;j++)
//            {
//                if (CityMap[i][j] == 1)
//                    x1 = i, y1 = j;
//                else if (CityMap[i][j] == 2)
//                    x2 = i, y2 = j;
//            }
//        }
//
//        return bfs(CityMap);
//    }
//};


//DP33 买卖股票的最好时机(四)
// https://www.nowcoder.com/practice/ba3c096c19e04afbbbd59250e909ac68?tpId=230&tqId=39770&ru=/exam/oj
//#include <iostream>
//#include <vector>
//
//using namespace std;
//
//const int N = 1010;
//
//int n, k;
//int p[N];
//
//int maxProfit()
//{
//   
//    //k = min(k, n / 2);
//    vector<vector<int>> f(n + 1, vector<int>(k + 1, -0x3f3f3f3f));
//    auto g = f;
//
//    f[0][0] = -p[0];
//    g[0][0] = 0;
//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = 0; j <= k; j++)
//        {
//            f[i][j] = max(f[i - 1][j], g[i - 1][j] - p[i - 1]);
//            g[i][j] = g[i - 1][j];
//            if (j >= 1)
//                g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + p[i - 1]);
//        }
//    }
//
//    int ret = 0;
//    for (int i = 0; i < g[n].size(); i++)
//    {
//        ret = max(ret, g[n][i]);
//    }
//
//    return ret;
//}
//
//int main()
//{
//    cin >> n >> k;
//    for (int i = 0; i < n; i++)
//        cin >> p[i];
//
//    cout << maxProfit() << endl;
//
//    return 0;
//}